#!/usr/bin/python
# -*- coding: utf8 -*-

def fib(n):
    """ Bottom-up """
    #  特殊情况： n为0或1
    if(n == 0):
        return 0
    elif(n == 1):
        return 1
    else:
        # 用f(0)表示F(n-2),f1表示F(n-1),f2表示F(n)
        f0 = 0
        f1 = 1
        f2 = f0+f1
        index = 2
        while(index < n):
            # 每个循环前进一步
            f0 = f1
            f1 = f2
            f2 = f0+f1
            index = index + 1
        return f2

